package Demo04.Demo010;

public class Test {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(4);
        ListNode listNode3 = new ListNode(5);
        listNode1.next = listNode2;
        listNode2.next = listNode3;

        ListNode listNode4 = new ListNode(1);
        ListNode listNode5 = new ListNode(3);
        ListNode listNode6 = new ListNode(4);
        listNode4.next = listNode5;
        listNode5.next = listNode6;

        ListNode listNode7 = new ListNode(2);
        ListNode listNode8 = new ListNode(6);
        listNode7.next = listNode8;

        ListNode[] listNodes = new ListNode[3];
        listNodes[0] = listNode1;
        listNodes[1] = listNode4;
        listNodes[2] = listNode7;
        ListNode newList = mergeKLists(listNodes);//打印合并后链表
        ListNode cur = newList;
        while (cur != null) {
            System.out.print(cur.val);
            System.out.print(" ");
            cur = cur.next;
        }
    }

    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        return merge(lists, 0, lists.length - 1);
    }
    public static ListNode merge(ListNode[] lists, int beg, int end) {
        if (beg == end) {
            return lists[beg];
        }
        int mid = beg + (end - beg) / 2;
        ListNode sortedList1 = merge(lists, beg, mid);
        ListNode sortedList2 = merge(lists, mid + 1, end);
        return mergeTwoList(sortedList1, sortedList2);
    }
    public static ListNode mergeTwoList(ListNode list1,ListNode list2){
        ListNode preNode = new ListNode(-1);
        ListNode tail = preNode;
        while (list1 != null && list2 !=null) {
            if ( list1.val < list2.val) {
                tail.next = list1;
                list1 = list1.next;}else {
                tail.next = list2;list2 = list2.next;
            }
            tail = tail.next;
        }
        if (list1 !=null){
            tail.next = list1;
        }else{
            tail.next = list2;}
        return preNode.next;
    }
}


